import javax.swing.*;
import java.awt.*;

public class algorithm {
    public static void main(String[] args) {
        int[] arr={1,4,10,23,45,47,50};
        //int index=BinarySearchRecursion(arr,0,arr.length-1,45);
        /*int index=BinarySearch(arr,45);
        if(index!=-1){
            System.out.println("找到要查找的值的下标为："+index);
        }else{
            System.out.println("不存在该数");
        }*/
        hanoiTower(3,'A','B','C');

    }
    //二分查找算法--递归
    public static int BinarySearchRecursion(int[] arr,int left,int right,int val){
        int mid=(left+right)/2;
        int midVal=arr[mid];
        if(left>right){
            return -1;
        }
        if(val<midVal){
            //说明要查找的值在左边
            return BinarySearchRecursion(arr,0,mid-1,val);
        }else if(val>midVal){
            //说明要查找的值在右边
           return BinarySearchRecursion(arr,mid+1,right,val);
        }else{
            //说明中间值刚好就是要查找的值
            return mid;
        }

    }
    //二分查找法--非递归
    public static int BinarySearch(int[] arr,int val){
        int left=0,right=arr.length-1,mid,midVal;//6
        while(left<=right){
            mid=(left+right)/2;
            midVal=arr[mid];//int[] arr={1,4,10,23,45,47,50};
            if(val<midVal){
                //在左区间
                right=mid-1;
            }else if(val>midVal){
                //在右区间
                left=mid+1;
            }else{
                return mid;
            }
        }
        return -1;

    }

    //分治算法解决汉诺塔问题
    public static void  hanoiTower(int num,char a,char b,char c){
        /*参数：1、num是指总盘子数 2、a是指开始塔 3、b是指辅助塔 4、c是指终点塔
        * */

        //思路：分两步：1、把第n-1个盘子放到b塔上，把第n个盘子放到c塔上，
        //             2、再把第n-1个盘子从b塔放到c塔上

        if(num==1){
            //只有一个盘子的情况：直接放到c盘上
            System.out.println("从"+a+"移动到"+c);
        }else{//盘子的数目>=2

            //现将n-1个盘子从塔a移动到塔b
            hanoiTower(num-1,a,c,b);//输出的一直是ac，所以将bc的参数互换
            System.out.println("从"+a+"移动到"+c);
            //再将塔b移动到塔c
            hanoiTower(num-1,b,a,c);
        }




    }



}
